This invention relates to a method, apparatus and data structure for object management, in the field of the object-based technology.
Section 1.2 Overview of Object-based Technology
Real world existence can be expressed using objects created on a computer, with xe2x80x9cobject-basedxe2x80x9d technology (C++ Programming Language, Second Edition, Bjarne Stroustrup, 1991, Preface to the first edition). These objects represent concepts, organizations and things in the real world.
Moreover, overall complex processing can be implemented, by invoking processes corresponding to messages (such as start signal, response, etc.) using object functions. This is called xe2x80x9cobject-oriented programmingxe2x80x9d (pp14, The C++ Programming Language, Second Edition, by Bjarne Stroustrup, 1991).
Various programming languages, such as Small Talk and Common Lisp Object System, have been developed to realize object-based programming technology. The most popular language is C++. With C++, it is possible to define xe2x80x9cClassxe2x80x9d as a model of objects and generate objects using a xe2x80x9cnewxe2x80x9d operator that secures memory.
The following sections describe problems relating to storage, reproduction and transmission of objects by reviewing the current object-based technology, such as object-oriented programming, Common Object Request Broker Architecture (CORBA), C++ language and object-oriented databases.
Section 1.3 Limits of Object-oriented Programming
In object-oriented programming, a procedure for generating objects is coded as logic of the programming. A sequence of processes starts when a message, expressing external input, is passed to an object. Objects to be generated by each program are already determined beforehand. Further objects are generated by program logic as a procedure, which is invoked by the external input or internal procedures.
Until now, there was no concept of xe2x80x9cFirst, prepare data that describe objects and relations among them. Then by reading the data, a computer reproduces a group of objects and invokes procedures defined by messages among these objects.xe2x80x9d
Section 1.4 Limitations of CORBA
Common Object Request Broker Architecture (CORBA) defines procedures for transmitting messages among objects, which are distributed among computers connected by a communications network. It is a concrete procedure, by which computers cooperate with each other and carry out procedures through a communications network. Here, a conventional object-oriented programming program generates objects in each computer.
Until now, there was no concept of the following. Prepare data of objects for each computer. A complex procedure can be implemented over the whole communications network, utilizing these data and messages are passed among objects in computers of this network so that each computer generates objects from the data.
Section 1.5 Limitations of C++ Language
C++ language has the widest scope of application as a means to implement object-based technology. The program of C++ language can be operated on a wide range of hardware since it can be converted to a program of C language. Java language employs same manner of handling Class and object.
However, the specification of C++ language does not refer to the mechanism of retaining objects. Using C++ language actually, one realizes how difficult it is to retain objects made by it. It is also difficult to retain a pointer that indicates object, since a pointer is an address of memory, to which the object was allocated. Even if the address of memory is retained, there is no guarantee that it will match-up with an address of object reproduced when the computer is invoked at the next time.
Many program languages can be used for object-based technology. However, there is no language that treats retention of objects and pointers. One has to device a dedicated mechanism saving key information of each specific application. There is no general method that retains objects and pointers.
Section 1.6 Limit of Object-oriented Database
An article, xe2x80x9cObject-oriented databasexe2x80x9d, Nikkei Intelligent Systems, Separated volume, Nikkei BP Company, 1994, states xe2x80x9cObject-oriented databases (OODB) appeared to permanently retain the application-objects that were developed by object-oriented technology. With object-oriented databases, it is possible to retain not only the object but also the mutual relationship among them.xe2x80x9d
However, an object-oriented database is a complex mechanism that controls data in the server computer and distributes it to client computers who use it. For this reason, an object-oriented database is expensive. For the current object-oriented database technology, it is not so easy to treat cases where data are distributed among computers connected by communications networks.
Also, the search procedure of an object-oriented database takes a lot of time, since it has to search all objects in order to find the specific objects satisfying assigned conditions. It is possible to prepare a group of objects satisfying some assigned conditions, in order to reduce search time. However, this requires an additional preparation procedure and memory to keep the results.
It is useful to have a simple technology that retains and reproduces an object (set), and transmits it to another computer and reproduces it there. It is also useful to have a technology that reproduces only objects necessary for the current procedure, which reproduces retained objects or reproduces them to another computer. Retrieving all objects into main memory, a computer encounters a problem that no other process can be invoked, if too many objects are interrelated. A small computer may not be able to reproduce all of these objects. It is convenient to have a simple technique that reproduces only objects necessary for the current procedure into main memory.
Section 7 shows Examples of Applications with These Technologies.
The present invention is a xe2x80x9csimple method that retains and reproduces (sets of objectsxe2x80x9d and a xe2x80x9csimple method that transmits and reproduces (sets of) objects.xe2x80x9d This is also a xe2x80x9ctechnique that produces necessary parts of an object set, according to developments of a computer process, by combining data dispersed across computers in a communications network.xe2x80x9d Details are shown below.
Section 3.1 Basics of Object Retention and Reproduction
Retaining an object can be done by writing out data included in this object, which exists in main memory, into a storage medium. Storage medium is a medium such as magnetic disk, magnetic tape, FD (floppy disk), writable CD-ROM, and SRAM. They retain data either temporarily or permanently. Some parts of main memory with a constant power supply can be used as a storage medium. Storage medium is sometimes called a secondary memory medium or external memory medium in contrast to main memory.
Through communications circuits, data (contents) of an object can be transmitted to other computers, where it is kept in the main memory or the external storage medium.
An object includes data as values of an integer, real number, character string or pointer. Object data, except for a pointer, can be simply written to a storage medium. An object sometimes includes another object. For example, in C++ and Java, (object of class can have an object of another class as a variable. Inner object data contained in an outer object is recursively written out, while writing the outer object data.
When reproducing an object using data stored in storage medium, or data through communications circuit or the user interface of a computer, first objects are generates from class, which is the model of the objects. When C++ class is defined as xe2x80x9cclass X{ };xe2x80x9d, the object of class X is generated by code xe2x80x9cX* CnewObj=new X;xe2x80x9d. This memory address, which is the top address of memory reserved for the object in main memory, is assigned to CNewObj.
In Java, the object of class X is generated by code xe2x80x9cX JnewObj=new X;xe2x80x9d. It is not possible to use pointers explicitly in Java. However, the Java virtual machine treats JNewObj as a pointer in the internal procedure. (Please refer to xe2x80x9cJava, Quick Reference, D. Flanagan, translated by Nagamatsu, O""Reiley Japan, Ohmu-sha 1996, p37xe2x80x9d.) As evidence of this inner mechanism, code xe2x80x9cX JNewObj2=JNewObj;xe2x80x9d results in that JNewObj and JNewObj2 indicate the same object.
After generating an object in memory, the procedure reads-in data recorded in storage medium and sets them as variables of the object. A memory address of this object is different from an address of the original object when data were output. However, meanings of the object are precisely reproduced.
It is possible to execute the above procedure if there is a definition to the class that is a model of the object, before reading-in object data from storage medium. For instance, an object can be made by code xe2x80x9cnew Xxe2x80x9d, because the definition of class X is already given.
If the program is coded to indicate the correspondence between a specific situation and class definition to be used for object generation, it can reproduce an object with an appropriate class definition. If there is only one class definition, then this class should always be used to reproduce objects. If there are multiple classes, it is possible to fix the order of class definitions to be used for object reproduction, by writing program code to follow this order and reproduce objects. It is also possible to assign class definition to each group of objects.
For a simple case, objects can be reproduced as mentioned above.
Section 3.2 Object Transmission and Reproduction, and Operator Input-output
In the procedure of object retention and reproduction, a computer outputs data of object data to be retained in storage medium of this or another computer. The computer reads-in this data and reproduces objects.
The object can be reproduced on another computer that reads-in these output data. That is, the file of output data is sent to another computer, and a process of this computer reproduces objects in its main memory. Instead of outputting object data in main memory to a file on its storage medium, the computer can send it to another computer through a communications circuit. An object can be reproduced on another computer using this data.
Outputting object data to storage medium is equivalent to transmitting it to the outside through a communications circuit. To show object data on a display unit of a computer is equivalent to transmitting object data to a human being. Data can be delivered to another computer using a portable medium such as FD. This is also equivalent to the procedure of outputting object data to a storage medium. Thus, it is possible to transmit object data and reproduce an object by a technique of retaining and reproducing objects.
The computer can generate objects using data from operators through the input unit or by reading in a data file created by editor software.
Section 3.3 Class Generation Data
Section 3.3.1 Class Identifier
When there are multiple classes of objects and the assignment of these classes cannot be specified in program logic, the method of section 3.1 is not applicable. Now, a xe2x80x9cprocedure to output a class identifier of an objectxe2x80x9d is introduced, in addition to the xe2x80x9cprocedure to output object data.xe2x80x9d In other words, a computer outputs a xe2x80x9cclass identifierxe2x80x9d when outputting data included in the object. For example, class X is defined by the following codexe2x80x9d
class X{public: cls-print( ){xe2x80x98output character string xe2x80x9cCLS_Xxe2x80x9dxe2x80x99;} };. The function c1-print( ) that outputs name of this class, is also defined. Outputting data included in object of class X, the procedure invokes cls-print( ) that outputs character string xe2x80x9cCLS_X.xe2x80x9d This character string is the class identifier.
When reproducing an object, the procedure generates an object by class definition corresponding to a class identifier read-in from a storage medium, and sets object data read in to this object. In the above example, memory is reserved by code xe2x80x9cnew Xxe2x80x9d for a character string xe2x80x9cCLS_Xxe2x80x9d. The object (contents) data read in are set in this memory.
In this case, code xe2x80x9cnew Xxe2x80x9d should be invoked for character string xe2x80x9cCLS_Xxe2x80x9d. It is necessary to define correspondence between definition of class X and character string xe2x80x9cCLS_Xxe2x80x9d in the program code. Suppose character string variable xe2x80x9cchar* cls_str,xe2x80x9d is set to an object identifier read in. The following code reserves memory for a new object using the definition of class X as a model. This memory address is set to xe2x80x9cnew_obj.xe2x80x9d
if(strcmp(cls_str,xe2x80x9cCLS_Xxe2x80x9d==0){new_obj=new X;}; Variable xe2x80x9cnew_objxe2x80x9d should be xe2x80x9cvoid *xe2x80x9d or a pointer to a base class of class X.
A number can be used as a class identifier. In this case, it is possible to write a switch code consisting of multiple codes like the if-statement mentioned above. Suppose identifier of class X is number xe2x80x9c1000xe2x80x9d and variable xe2x80x9cint nxe2x80x9d is set to the read-in number. The procedure can generate an appropriate object with the following switch statement.
switch(n){case 1000: new_obj=new X; break; . . . }
This description calls the combination of class identifier (e.g. xe2x80x9cCLS_Xxe2x80x9d) and class generation code (e.g. xe2x80x9cnew Xxe2x80x9d) xe2x80x9cclass generation data.xe2x80x9d
Section 3.3.2 Handling of Class Generation Data
When a program has class generation data, it can easily generate objects from class identifiers read in. Even if a program has no class generation data, it can generate objects form class generation data of a dynamically linked program (e.g. a DLL file). It is possible to supply up-to-date class generation data by replacing this dynamically linked program.
A program can read-in a function recorded in the objective file and set this address to a function pointer. With this function pointer, it can invoke a function just read in. There is an example in xe2x80x9cAdvanced C++, Programming Styles and Idioms, J. O. Coplien, 1992, p328xe2x80x9d. Reading-in a new function that has a new class generation data, the procedure can generate an object using the new class generation data. The task of generating an object from the class identifier is assigned to the function just read in.
It is possible to define general class definition with a general data structure and a general member function that invokes a function set to a function pointer. A program can generate objects using this general class definition and customize this object by setting the function pointer to a function just read in (without stopping this program). In this case, new xe2x80x9cclass generation dataxe2x80x9d is defined as a xe2x80x9ccombination of the class generation data of the general class and objective file of the functionxe2x80x9d.
In Java, the process can be linked with the class dynamically. Please refer to xe2x80x9cJava, Quick Reference, D. Flanagan, O""Reiley Japan, Ohmu-sha, 1996, p14xe2x80x9d.
Section 3.3.3 Reading in Class Identifier
Object data including a class identifier is temporarily output to storage medium. These data are read-in at another time and then objects are reproduced. There is a case where class identifier and content data of an object is received from outside through a communications circuit. In this case, the original data could be either in main memory of a sending computer or in a secondary storage unit. Furthermore, there are cases where the procedure reads-in a file that is created by editor software and stored in a storage medium, or where the procedure receives data from an operator through an input interface.
In each case, the procedure generates an object from the class identifier, and also sets the content data. In order to simplify the above-mentioned procedure of object reproduction, it is convenient if the order of data recording is as follows. First, class identifier of an object is recorded and then other object data are recorded successively. However, even if the order is reversed, the procedure can handle them by temporarily saving the object data. That is, object is first reproduced from the class identifier read-in, and contents of this object are set by the saved object data. It is also possible to write the class identifier to one file and the object data to another file. The procedure reads-in both files and synchronizes them to generate objects and to set object data.
Section 3.4 Problems of Pointer Retention, Reproduction and Transmission
There are three cases where pointers are used. The first case is, as shown in FIG. 1(1), the one to one mapping between pointer (P1 pointer 101) and the pointed object (X1 object 102). In this case, object data of X1 object 102 can be output, instead of outputting memory address of X1 object indicated by P1 pointer 101. For reproducing this pointer, first, the procedure generates the object and assigns its memory address to P1 pointer. Then the procedure reads-in object data of X1 object 102 from the storage medium and sets them to the object generated. P1 pointer 101 pointing to X1 object 102 is reproduced.
The second is the case where multiple pointers point one object. In FIG. 1(2), all three of P2 pointer 103, Q2 pointer 104 and R2 pointer 105 indicate X2 object 106. In this case, the problem is which pointer should be assigned to cope with outputting object data of X2 object 106 and reproducing it. If P2 pointer 103 is assigned, it is necessary to copy this value, which is memory address of X2 object 106, to Q2 pointer 104 and R2 pointer 105. In other words, it is necessary to analyze the structure of an application program and to implement a customized procedure to retain and reproduce pointers.
In addition to the possibility that P2 pointer 103, Q2 pointer 104, and R2 pointer 105 point to X2 object 106, there is another possibility that some of them point to other objects according to situations of the application. The procedure to retain and reproduce a pointer becomes more difficult in this case. It is necessary to change the job assignment of outputting and reproducing X2 object 106, according to the situation. A procedure to copy the pointer value to other pointers should be also changed according to the situation. Furthermore, it is necessary to cope with the case where none of these pointers indicate X2 object 106.
The third case is where one pointer might indicate one of multiple objects. FIG. 1(3) shows there are possibilities that P3 pointer 107 indicates X3 object 108, Y3 object 109, or Z3 object 110. Though the C++ type check is strict, there is no problem when P3 pointer 107 points to the base class of X3 object 108, Y3 object 109 and Z3 object 110, even if they are different classes. P3 pointer 107 can point to one of these three objects. If the type of P3 pointer 107 is xe2x80x9cvoid*xe2x80x9d, it is possible to assign an object address of any class to P3 pointer 107.
Though it is easy to output object data pointed to by P3 pointer 107, it is impossible to identify a class definition when reproducing an object after reading-in the data. That is, it is impossible to reproduce P3 pointer because there is no data indicating which class definition should be used among classes of X3 object 108, Y3 object 109 and Z3 object 110.
Problems become more complicated in the case where the second and the third are mixed.
There is another case where pointer of A object points to B object, pointer of B object points to C object and pointer of C object points to A object. This case where objects point one after another in a circle, causes a problem as to in what order the object should be reproduced.
Object data sometimes include pointers. Object retention, reproduction and transmission is incomplete, if pointer retention, reproduction or transmission is impossible. Sometimes it is necessary to retain, reproduce and transmit a pointer that belongs to no object.
Section 3.5 Object Tree and Pointer that can be Retained, Reproduced and Transmitted
Since the value of pointer is just an address of memory, there is no meaning to retain, reproduce and transmit the pointer itself. The present invention introduces a method to convert a pointer to data identifying the pointed object and a method to convert the data back to the pointer. By sending this data to another computer, the pointer will be sent. Thus, it is possible to implement pointers that can be retained, reproduced and transmitted.
The exact meaning of sending pointer is reproducing a pointed object and pointer that points this object in the receiving computer. In short, it means sending a pointer of equivalent meaning. It is useless to send just the value of the pointer, which is merely a memory address of the sending computer.
Section 3.5.1 Object Tree
An object management method should be first devised, in order to implement pointers that can be retained, reproduced and transmitted. A memory address is only the access method to an object immediately after its generation. A memory address is given by the code xe2x80x9cnewxe2x80x9d to generate an object or by the code xe2x80x9cmallocxe2x80x9d to reserve memory.
The present invention manages memory addresses of objects as a set. Though an actual element of set is a memory address, we call this set an xe2x80x9cobject setxe2x80x9d for simplicity. Sometimes the memory address of an object is simply called xe2x80x9cobject.xe2x80x9d
The object set should be accessible to each object. That is, the object set can be implemented as a simple list, a bidirectional list, an array, a hashed array, a binary tree, bag, stack, queue, dictionary (set of association), and so on. A hashed array is a collection of lists of objects with same hashed number, where these lists are arrayed in order of their hashed number. These sets provide access methods to find and access the target object by tracing list elements, accessing a list of assigned hashed numbers, tracing tree branches, and so on.
An xe2x80x9cObject identifierxe2x80x9d, which will be defined later (in section 3.5.2), could be used as a key to find out the target object. Sequentially checking objects in an object set, the procedure can find out the object that matches the assigned object identifier. It is a well known method to limit the search range by calculating a hashed number from the assigned object identifier. A hashed array uses this method. Any set can implement an object set, if any element of this set can be accessed.
The present invention introduces an object that manages an object set. This object is called a xe2x80x9cmanagement objectxe2x80x9d and has data specifying the managed set. For instance, the management object holds a pointer (xe2x80x9cobject set pointerxe2x80x9d 503 of FIG. 5) that keeps an address of list head 506, which indicates the top of an object set. By repeating a procedure which assigns a management object to a set of management objects, it is possible to put objects (mainly management objects) in a tree structure. The present invention calls this as an xe2x80x9cobject tree.xe2x80x9d
Examples shown in this description assume that the management object carries not only data to manage an object set but also data as an object itself. In other words, xe2x80x9cmost of the objects to be retained and transmitted by the present invention are management objects that have data for managing an object set and data as a normal object.xe2x80x9d Management objects as well as normal objects are simply called objects.
However, the present invention can be applied without any modification to the case where a xe2x80x9cmanagement object holds only the data to manage an object set,xe2x80x9d and xe2x80x9cobject data representing the subject matter are dealt with only by normal objects, not by management objects.xe2x80x9d A pointer can be set from an exclusive management object to a normal object.
FIG. 2 shows an example of an object tree. The a0 list head 203 corresponds to a0 object 201. In order to express this relation, an address of a0 list head 203 is set to pointer (object set pointer 503) held by a0 object 201. In the following, xe2x80x9clist head corresponds to an objectxe2x80x9d means that the address of the list head is set to the pointer (object set pointer 503) held by the object. The list, that starts from a0 list head 203, accommodates a1 object 204 and a2 object 205. This list is the object set 202 corresponding to the a0 object. The xe2x80x9ca1 objectxe2x80x9d 204 corresponds to the a1 list head 207. A list starting from this list head accommodates a3 object 208, a4 object 209 and a5 object 210. This list is the object set 206 corresponding to a1 object 204. The xe2x80x9ca2 objectxe2x80x9d 205 corresponds to the a2 list head 212. A list with this list head accommodates a6 object 213. This list is the object set 211 corresponding to the a2 object 205.
A minimum structure of an object tree is one-leveled. An example of an object tree with the minimum structure consists of only a0 object 201 and the corresponding object set 202. Though FIG. 2 shows a two-leveled structure, it is possible to add other levels if necessary. The tree can be a structure with a different number of levels for each branch. An example is the tree structure without object set 211 corresponding to a0 object.
Section 3.5.2 Object Identifier
Each object in the object tree has data to distinguish itself from the other objects. This data is called an xe2x80x9cobject identifier.xe2x80x9d The object identifier could be either a character string (i.e. name of object) or a number. It is possible to introduce a new variable as an object identifier. This variable can be set to a character string, or number. It is also possible to use a variable that already exists as an object identifier.
Providing a unique name to each object set that accommodates objects, means that a combination of object identifiers can identify a specific object. In FIG. 2, object identifier is the name assigned to each object. Combination (a0, a1, a5) identifies a5 object 205.
In the example of FIG. 2, the object""s name is unique among all objects. It is Possible to use the same name for different objects that belong to different object sets without any trouble, if we use a combination of object identifiers to identify an object. For instance, even if the name of a6 object 213 is changed to xe2x80x9ca5xe2x80x9d, (a0, a2, a5) identifies a6 object 213 and (a0, a1, a5) identifies a5 object 210. There is no confusion between a5 object 210 and a6 object 213, because of the difference in combinations of the object identifiers.
When using the same object identifier (name in FIG. 2) in one object set, plural objects can be identified by a combination of object identifiers. The same identifier in one object set may be acceptable, depending on the Purpose of application or the design principles, such as to treat all objects of the same object identifier in exactly the same manner.
It is possible to omit the character string xe2x80x9ca0xe2x80x9d to specify an object in an object tree, since any combination for the object in FIG. 2 starts with a0. For example, a5 object 210 can be identified by (a1, a5). Moreover, it is possible to omit a0 object 201 itself from the object tree. However, the structure starting with a0 list head 203, which corresponded to a0 object 201, should be left. FIG. 3 shows an object tree without the root object (object equivalent to a0 object 201 of FIG. 2).
Section 3.5.3 Pointer Retention, Reproduction and Transmission
The previous section explained that a combination of object identifiers can identify an object. If there is a procedure that converts a pointer to a continuation of object identifiers, it is possible to substantially retain pointer data by outputting a series of object identifiers to a storage medium. It is possible to retain and transmit a series of object identifiers that identifies the object pointed to.
Moreover, it is possible to reproduce a pointer by reading the retained pointer data, if there is a utilizing procedure to identify an object by a combination of object identifiers. It is possible to reproduce a pointer whenever necessary, if we have data to identify the pointed object. By transferring a combination of object identifiers, it is possible to virtually transmit and reproduce pointers.
The procedure reads-in data from a file in storage medium or data from other computers, and reproduce an object tree while reproducing objects. The procedure reproduces the object tree, coupling each management object and each object set to be managed by the management object.
Pointer data expressed as a continuation of object identifiers is called xe2x80x9ctranslated pointer dataxe2x80x9d 402 and is handled together with the pointer. A pointer to be retained, reproduced and transmitted should be associated with xe2x80x9ctranslated pointer dataxe2x80x9d 402. FIG. 4 shows an example. Translated pointer data 402 is combined with the pointer 401, which is the subject of retention, reproduction and transmission. This is the pointer structure 406. This structure can be defined as a class. Translated pointer data 402 consists of a series of object identifiers, from the first object identifier 403 to the n-th object identifier 405 in FIG. 4.
When a pointer to an object accommodated in the object tree is retained, a procedure is invoked to output translated pointer data that is a series of object identifiers to identify the pointed object. The procedure reads this data and holds it as translated pointer data 402. In the pointer structure 406 of FIG. 4, translated pointer data 402 holds the list structure that keeps the order of object identifiers.
It is convenient to set no value for pointer 401 immediately after reading translated pointer data. That is, the value of pointer 401 should kept as zero. Generally it is always possible to obtain a pointer value from translated pointer data, after the pointed object is reproduced in the object tree. However, it is a complicated job to check for every pointer whether or not the pointed object is already reproduced. After a whole object tree is reproduced, it is also possible to obtain all pointer values. Please note that the whole (in actual fact, most) of the object trees are reproduced if all of the pointer structure is converted to pointers. This is inconvenient from the point of view of reproducing only necessary parts of the object tree.
It is possible to achieve the goal of reproducing only necessary parts of an object tree, if the translated pointer data is converted to a pointer at the time of using the pointer. A detailed procedure is as follows. When finding out that the value of pointer 401 in the pointer structure is set to zero, the procedure traces objects in the object tree by using a series of identifiers and identifies the pointed object. The address of this object is the value of the pointer to be obtained. After setting this address to the pointer, the procedure can access the pointed object efficiently.
It is possible to omit pointer 401 from the pointer structure 406 and to introduce a procedure to search for the object in the object tree whenever the pointer is necessary. This reduces the memory size down to the limit.
If an object tree is reproduced in another computer and a series of object identifiers are sent to this computer, a copy of a pointer can be made by this computer. That is, it is possible to transfer a pointer without logical contradictions.
Even if there is no procedure to retain pointer data, it is possible to set a pointer by reading a series of object identifiers written by editor software to a file in storage medium. It is also possible to obtain a pointer from a series of object identifiers input by am operator through an input interface.
Section 3.4 showed problems in the former technology in the method of retaining and reproducing pointers. These problems exist in the case where plural pointers specify a single object (FIG. 1(2)), the case where a single pointer has the possibility of pointing to plural objects (FIG. 1(3)), and the case in which this two situations are mixed. Even for such cases, it is possible to retain, reproduce and transmit pointers without any problem, by introducing an object tree and converting the pointer to translated pointer data.
Section 3.6 Object Retention, Reproduction and Transmission
It is possible to retain, reproduce and transmit a pointer that points to an object accommodated in an object tree, by introducing an object tree and object identifiers. In other words, if there is a pointer to be retained, reproduced or transmitted, the pointed object should be accommodated in the object tree. In addition to the introduction of the class identifier in Section 3.3, these techniques make it possible to retain, reproduce and transmit objects including a pointer.
In order to retain object data, the procedure outputs a class identifier, object identifier and other content data, such as a character string, integer value, real number value, and so on. For the pointer to an object accommodated in an object tree, the procedure outputs the translated pointer data, that is a combination of object identifiers, and designates the pointed object. The procedure first outputs object data to a file and sends it by a communications circuit or by storage medium such as FD. It is also possible to send content of main memory directly through a communications circuit.
In order to reproduce objects from the data, the procedure reads-in the data from the file (or from other computers or from storage medium such as FD). Through this procedure, the object tree is also reproduced.
The procedure reads-in translated pointer data that is a series of object identifiers, and keeps it in conjunction with the pointer. For instance, it is recorded as translated pointer data of a pointer structure. Translated pointer data is also converted into a pointer, when the application program needs this pointer.
Section 3.7 Efficient Search
The search procedure of an object-oriented database takes a massive amount of time, since it has to search all objects to find specific objects satisfying assigned conditions. It is possible to prepare a group of objects satisfying some conditions, in order to reduce search time. However, this requires an additional preparation procedure and memory to keep the results.
On the other hand, the present invention accommodates objects in an object tree. It is possible to gather objects with a high possibility of being in the range of one search, and put them in to a single set. This simplifies the search.
If objects in object set 206 corresponding to a1 object in FIG. 2 were to be searched, first a1 object 204 is identified by the combination (a0, a1) and a1 list head 207 is found. Next objects linked to a1 list head 207 are sequentially fetched and investigated. Here, the object tree structure that accommodates objects is also utilized to limit the range of the search. This is a good point of the present invention compared with an object-oriented database. Efficient search is realized without either additional procedures or memory. These overheads would normally be expected for an object-oriented database that is designed for general use.
The key to accomplishing simple and efficient (that is high speed) searching is to collect objects, that have high possibilities of being in one investigation range, into a single set. In many cases, by analyzing an application, it is easy to find out the object set with a high possibility of being in one investigating range.
For instance, an application, which deals with models of communications networks, often searches all communications links of an assigned communications network. Sometimes it searches all nodes of a communications network. FIG. 3 shows an example of arranging these groups as sets.
The list head 301 of FIG. 3, the root of the object tree, accommodates Network object 302 named xe2x80x9cX communications networkxe2x80x9d and Network object 303 named xe2x80x9cY communications network.xe2x80x9d The list head 304, that is corresponding Network object 302, accommodates a Network management object named xe2x80x9cLink managementxe2x80x9d 305 and a Network management object named xe2x80x9cNode managementxe2x80x9d 306. The head 311, that is corresponding to Network management object 305, accommodates Link object 312 named xe2x80x9cTokyo⇄New York,xe2x80x9d Link object 313 named xe2x80x9cNew York⇄Londonxe2x80x9d and Link object 314 named xe2x80x9cLondon ⇄Tokyo.xe2x80x9d The list head 307, that is corresponding to Networ management object 306, accommodates Node object 308 named xe2x80x9cTokyo,xe2x80x9d Node object 309 named xe2x80x9cNew Yorkxe2x80x9d and node object 310 named xe2x80x9cLondonxe2x80x9d.
Since the root object (i.e. a0 object 201 in FIG. 2) of the object tree of FIG. 3 is omitted (See Section 3.5.2), the series of object identifiers to identify the object in the object tree start with xe2x80x9cX communications networkxe2x80x9d of Network object 302 or xe2x80x9cY communications networkxe2x80x9d of Network object 303.
When investigating all link objects of X communications network, first, network management object 305 of name xe2x80x9cLink managementxe2x80x9d is identified by the combination (xe2x80x9cX communications networkxe2x80x9d and xe2x80x9cLink managementxe2x80x9d), and then the corresponding list head 311 is designated. After that, link objects following this list head are investigated in order.
When investigating all link and node objects of X communications network, first, Network object of name xe2x80x9cX communications networkxe2x80x9d is identified by the combination (xe2x80x9cX communications networkxe2x80x9d). Then network management objects and objects contained in them are all investigated. This makes the search easy if the target objects to be investigated are gathered in a certain branch of object tree.
When searching link objects of all communications networks, the procedure can trace the object tree by Depth First Search. When network management object of xe2x80x9cLink managementxe2x80x9d is reached, the corresponding object set is investigated, and the search moves to the next branch. When network management object of xe2x80x9cNode managementxe2x80x9d is reached, the search for this branch is skipped and the search moves to the next branch again.
Sometimes a huge quantity of memory is required to reproduce all related objects in main memory, to read-in object data recorded in storage medium or object data held by another computer. It is convenient just to reproduce the minimum objects necessary for the immediate procedure and then increase objects reproduced according to the development of the procedure.
The following sections shows ways of reproducing only the necessary part of an object tree and increasing it according to the requests, instead of reproducing the whole object tree at once.
Section 4. 1 Partial Read-in of Object Tree
Suppose all data of the object tree in FIG. 2 are recorded in file F, and suppose the first procedure stage of an application program needs only a1 object 204 and a2 object 205, which are managed by a0 object 201, and a0 object 201. In this case, this application program reproduces only a0 object 201, a0 list head 203, a1 object 204 and a3 object 205 and ignores other data while reading file F.
Assume translated pointer data is (a0, a1, a5). The procedure traces a0 object and a1 object on the object tree, to find the pointed object. While trying to identify a5 object, the procedure realizes that there is no branch of object tree beyond a1 object so the procedure reads-in file F again and reproduces the branch beyond a1 object. After this, the procedure identifies a5 object and gets the address of a5 object, which is the conversion result of the translated pointer data (a0, a1, a5). Here, data beyond a2 object are ignored again.
It is possible to assign how far the object tree should be reproduced when reading-in file F, such as a level number to be reproduced ahead.
Section 4.2 File Division
It is possible to divide a file, to which the procedure outputs data of object tree, into files consisting data to be read-in at one time. This makes the read-in procedure simple. An example using FIG. 2 is as follows. The xe2x80x9cdata of a1 object 204 and a2 object 205 are stored in file F0.xe2x80x9d The xe2x80x9cdata of a3 object 208, a4 object 209 and a5 object 210 to File F1xe2x80x9d and xe2x80x9cdata of a6 object 213 are stored to File F2.xe2x80x9d
The first step of reproducing the object tree is to make only a0 object, which is a management object 501. The file assignment data 504 of this management object is set to file F0 assigned from the outside. While obtaining the pointer from the translated pointer data (a0, a1), the procedure reads F0 and reproduces a1 object 204 and a2 object.
To describe details of a1 object 204 at this moment, FIG. 5 shows the structure of the management object. Management object 501 comprises xe2x80x9cobject set management dataxe2x80x9d 502, which is data as a management object, and xe2x80x9cindividual object dataxe2x80x9d 505, which is data as a normal object. xe2x80x9cObject set management dataxe2x80x9d 502 comprises xe2x80x9cobject set pointerxe2x80x9d 503, xe2x80x9cfile assignment dataxe2x80x9d 504, xe2x80x9cread-in settled flagxe2x80x9d 507, modified data flagxe2x80x9d 508 and xe2x80x9cchild object existence flagxe2x80x9d 509. The xe2x80x9cobject set pointerxe2x80x9d 503 is set to the address of the corresponding list head 506 when this list head is generated, though the initial value of this pointer is zero. The object set pointer 503 of a1 object in FIG. 2 is set to the address of a1 list head 207 when this list head is generated.
Immediately after the file F0 is read in, xe2x80x9ca1 list head 207xe2x80x9d does not exist and the value of xe2x80x9cobject set pointerxe2x80x9d 503 of a1 object 204 is zero. Here, xe2x80x9cfile assignment dataxe2x80x9d 504 is set to indicate file F1, which has object data beyond a1 list head. This file assignment data belongs to a1 object, and is a part of data recorded in file F0. The xe2x80x9cread-in settled flagxe2x80x9d 507 is off (initial value), since no data in file F1 is read-in yet.
The xe2x80x9cmodified data flagxe2x80x9d 508 is also off, because any data which is read-in from the file indicated by file assignment data 504 has not been modified. This flag is used to determine whether or not the management object should be registered in the object list to be output (Section 0.5.5.1).
xe2x80x9cOn (Yes)xe2x80x9d or xe2x80x9coff (No)xe2x80x9d of xe2x80x9cChild object existence flagxe2x80x9d 509 indicates the presence of child objects. It is used to control the read-in procedure, when there is no file assignment data (Section 5.6.4.).
Assume translated pointer data is (a0, a1, a5). The procedure traces a0 object and a1 object of the object tree to designate the pointed object and realizes that the value of object set pointer of a1 object is zero. Judging that there is nothing more on the object tree, the procedure first generates a1 list head 207 and sets this address to the object set pointer 503. Next, the procedure opens and reads file F1, which is assigned to file assignment data 504 of a1 object 204, and sets the xe2x80x9cread-in settled flagxe2x80x9d 507 to on. Read-in settled flag 507 will be used by xe2x80x9cprocedure to generate and accommodate new objectxe2x80x9d of section 5.4. Since data of a3 object, a4 object and a5 object are recorded in file F1, these objects are reproduced and accommodated in the list starting from a1 list head 207. The xe2x80x9cchild object existence flagxe2x80x9d 509 of a1 object is also set to on.
Similarly, a2 object has file assignment data of F2. When obtaining a pointer from translated pointer data (a0, a2, a6), the procedure reads in F2 file and reproduces the object tree beyond a2 object.
Assume that only a0 object exists, and a procedure to obtain a pointer from translated pointer data (a0, a1, a5) is invoked. During this procedure, file F0 and file F1 are read in and xe2x80x9cobject set 202 corresponding to a0 objectxe2x80x9d and xe2x80x9cobject set 206 corresponding to a1 objectxe2x80x9d are reproduced.
A procedure outputting the content of the object tree is invoked with a management object assigned. There are three concrete procedures shown.
The first procedure is as follows. When a0 object 201 is assigned, file F0 designated by its file assignment data 504 is opened and data of objects managed by a0 object is output. Suppose that another file assignment data 504 (file F1) is found, while the content of a1 object is output to file F0. Data of the objects (following a1 list head) managed by al object is output to F1, which is another file opened. Also, data of objects managed by a2 object is written into file F2. If the file to be written is into is on another computer, data is sent to this computer and an output procedure to the file of the computer is invoked.
Suppose that different file assignment data 504 (file F1) is found, while the content of a1 object is output to file F0 in the above procedure. The a1 object is registered to the object list 1501 to be output. The procedure outputting the content of the object tree is invoked again with registered management objects.
The third procedure is as follows. This procedure first searches the object tree and registers management objects, that should be assigned to the output procedure, in the object list to be output 1501. Registered management objects are assigned in order and the output procedures for the content of object tree are invoked. Here, if the procedure encounters different file assignment data 504 (file F1), it skips the output of the corresponding object set. The details will be shown in Section 5.5.
Section 4.3 Timing for Converting Translated Pointer Data into a Pointer
In the case of reproducing only necessary parts of an object tree, it is advisable to invoke the procedure to convert translated pointer data into a pointer when the pointer becomes necessary for the application program. If all translated pointer data are developed at one time in the first stage of the procedure of application program, it will reproduce the whole (or most) of the object tree at one time.
Section 4.4 Part release of Object Tree
When the main memory is insufficient, a less frequently used part of the object tree should be output into a file and released (deleted) from main memory. As a result of this release, all branches ahead of the designated object set of the object tree will be released.
Releasing a1 list head 207 and the following, data of a3 object 208, a4 object 209 and a5 object 210 are written down to file F1 that is specified by file assignment data 504 of the content of a1 object 204. If xe2x80x9cmodified data flagxe2x80x9d 508 is off, there is no need to output because the content of file F1 has not been changed. Also, all objects following a1 list head 207 are released, and object set pointer 503 is set to zero.
Furthermore, the pointer structure 406 pointing to a released object (a3 object 208, a4 object 209 or a5 object 210) is initialized. That is, pointer 401 is set to zero. If translated pointer data 302 is empty, it should be set before releasing a1 list head and subsequent items.
The usage frequency of objects and object sets could be good information for deciding which part of object tree should be released. If the file is divided, the usage frequency of each file should be observed. Another method is to release parts of the object tree, disregarding the usage frequency.
If the file is not divided, there is one file retaining the data. The procedures mentioned above still can be applied, if parts of the object tree to be released are determined beforehand.
Section 4.5 File Dispersion on the Network
If computers are connected by a communications network, files containing object data can be dispersed over multiple computers. For example, file F0 is in computer A, file F1 is in computer B having a domain name www.atele.com, for example, and file F2 is in computer C. In order to use them in computer D, it is necessary to inform computer D that file F0 exists in computer A.
One example of this assignment is xe2x80x9chttp://www.atele.com/abc/F1xe2x80x9d. This shows that there is a file designated by the path xe2x80x9c/abc/F1xe2x80x9d in the computer designated by the domain name www.atele.com and the content of this file is transmitted by http communications protocol (running on the default port number for http). Indication of a file is generally composed of data that designates a computer (domain name, etc), and data that designates a file in the computer (file path, etc). The procedure (http, etc) that transmits information can be added in this assignment.
Assume that object assignment is the same as Section 4.2. The file assignment data 504 of a1 object 204 is xe2x80x9chttp://www.atele.com/ abc/F1xe2x80x9d at the time of reading file F0. At the time of converting translated pointer data to a pointer, contents of the assigned file are read and used for reproducing an object tree.
When writing out the contents of the object tree to a file, or when reading in the file, access authorization will be important. A UNIX computer can assign various kinds of permission data to files and control writing and reading. For example, suppose that object tree in FIG. 2 is reproduced on computer D and a5 object 210 is changed. Or, suppose that a7 object is added to a5 object 210. To save these changes, the procedure checks the file assignment data 504 of a1 object 204 and there it finds that xe2x80x9chttp://www.atele.com/abc/F1xe2x80x9d is set. The procedure asks the computer xe2x80x9chttp:/ /www.atele.comxe2x80x9d, about writing permission to xe2x80x9c/abc/F1xe2x80x9d. If this writing is prohibited, the procedure has to abandon the output.
If the procedure cannot abandon the output, it writes to another file using the following procedure. File assignment data 504 of a1 object 204 is changed to another file pass in computer D, such as xe2x80x9c/at1/abc/F1-newxe2x80x9d. The procedure outputs the data to this file. If the application program generates file F1-new, (usually) there is no problem to write in this file.
Since the content (file assignment data) of a1 object changes at this time, it is necessary to pay attention to the fact that the data to be output to file F0 also changed.
It is also possible to output the data to the file of another computer using handling permissions. The http procedure is a procedure that fetches and sends (and receives) data and has no procedure assigned as to how to write into a file. It is therefore necessary to invoke an exclusive writing procedure in the computer that holds the target file. It is also possible to reconstruct the http communication program and add function output to files.